package com.zjsru.oneDay202209;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: likew
 * @Date: 2022/9/22
 * 能否连接形成数组
 * 请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。
 *
 * 输入：arr = [15,88], pieces = [[88],[15]]
 * 输出：true
 * 解释：依次连接 [15] 和 [88]
 *
 * 输入：arr = [49,18,16], pieces = [[16,18,49]]
 * 输出：false
 * 解释：即便数字相符，也不能重新排列 pieces[0]
 *
 * 输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
 * 输出：true
 * 解释：依次连接 [91]、[4,64] 和 [78]
 *
 */
public class CanFormArray {
    /**
     * hash表
     * */
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int n = arr.length, m = pieces.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            map.put(pieces[i][0], i);
        }
        for (int i = 0; i < n; ) {
            if (!map.containsKey(arr[i])) {
                return false;
            }
            int j = map.get(arr[i]), len = pieces[j].length;
            //j 已经是由map的i分组所得到的，所以i + k即是在 pieces[j][？]开头的数组之中
            for (int k = 0; k < len; k++) {
                if (arr[i + k] != pieces[j][k]) {
                    return false;
                }
            }
            i = i + len;
        }
        return true;
    }
    
    /**
     * 排序 + 二分
     */
    public boolean canFormArray2(int[] arr, int[][] pieces) {
        int n = arr.length, m = pieces.length;
        Arrays.sort(pieces, (a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; ) {
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (pieces[mid][0] <= arr[i]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int len = pieces[r].length, idx = 0;
            while (idx < len && pieces[r][idx] == arr[i + idx]) {
                idx++;
            }
            if (idx == len) {
                i += len;
            } else {
                return false;
            }
        }
        return true;
    }
    
    
    public static void main(String[] args) {
        CanFormArray canFormArray = new CanFormArray();
        int[] arr =new int[]{91,4,64,78};
        int[][] pieces = new int[][]{{78},{4,64},{91}};
        System.out.println(canFormArray.canFormArray(arr, pieces));
    }
}
